We consider learning under the constraint of local differential privacy (LDP). For many learning problems known efficient algorithms in this model require many rounds of communication between the server and the clients holding the data points. Yet multi-round protocols are prohibitively slow in practice due to network latency and, as a result, currently deployed large-scale systems are limited to a single round. Despite significant research interest, very little is known about which learning problems can be solved by such non-interactive systems. The only lower bound we are aware of is for PAC learning an artificial class of functions with respect to a uniform distribution (Kasiviswanathan et al., 2008).

Summary of Contributions: UPDATE: I have read the author rebuttal and my review is unchanged. This work considers the role of interaction in (distribution-free) PAC learning with local differential privacy (LDP). In this model the learning algorithm only has access to examples that have been locally randomized in a differentially private way; the learner may specify the index of the example and the randomizer. If the learning algorithm makes all of its queries in advance, it is non-interactive, and if it makes its queries independent of the labels returned by the oracle, it is label-non-adaptive. The main results of this paper show that PAC learning with a label-non-adaptive LDP algorithm is characterized (up to polynomial factors) by the margin complexity MC(C) of the class, which is the inverse largest margin of separation achievable by linearly separable (into positive and negative examples) embedding of the domain.

We consider learning under the constraint of local differential privacy (LDP). For many learning problems known efficient algorithms in this model require many rounds of communication between the server and the clients holding the data points. Yet multi-round protocols are prohibitively slow in practice due to network latency and, as a result, currently deployed large-scale systems are limited to a single round. Despite significant research interest, very little is known about which learning problems can be solved by such non-interactive systems. The only lower bound we are aware of is for PAC learning an artificial class of functions with respect to a uniform distribution (Kasiviswanathan et al., 2008).

We consider learning under the constraint of local differential privacy (LDP). For many learning problems known efficient algorithms in this model require many rounds of communication between the server and the clients holding the data points. Yet multi-round protocols are prohibitively slow in practice due to network latency and, as a result, currently deployed large-scale systems are limited to a single round. Despite significant research interest, very little is known about which learning problems can be solved by such non-interactive systems. The only lower bound we are aware of is for PAC learning an artificial class of functions with respect to a uniform distribution (Kasiviswanathan et al., 2008).